“Clustering” generally refers to a computer system organization where multiple computers, or nodes, are networked together to cooperatively perform computer tasks. An important aspect of a computer cluster is that all of the nodes in the cluster present a single system image—that is, from the perspective of a user, the nodes in a cluster appear collectively as a single computer, or entity.
Clustering is often used in relatively large multi-user computer systems where high performance and reliability are of concern. For example, clustering may be used to provide redundancy, or fault tolerance, so that, should any node in a cluster fail, the operations previously performed by that node will be handled by other nodes in the cluster. Clustering is also used to increase overall performance, since multiple nodes can often handle a larger number of tasks in parallel than a single computer otherwise could. Often, load balancing can also be used to ensure that tasks are distributed fairly among nodes to prevent individual nodes from becoming overloaded and therefore maximize overall system performance. One specific application of clustering, for example, is in providing multi-user access to a shared resource such as a database or a storage device, since multiple nodes can handle a comparatively large number of user access requests, and since the shared resource is typically still available to users even upon the failure of any given node in the cluster.
Clusters typically handle computer tasks through the performance of “jobs” or “processes” within individual nodes. In some instances, jobs being performed by different nodes cooperate with one another to handle a computer task. Such cooperative jobs are typically capable of communicating with one another, and are typically managed in a cluster using a logical entity known as a “group.” A group is typically assigned some form of identifier, and each job in the group is tagged with that identifier to indicate its membership in the group.
Member jobs in a group typically communicate with one another using an ordered message-based scheme, where the specific ordering of messages sent between group members is maintained so that every member sees messages sent by other members in the same order as every other member, thus ensuring synchronization between nodes. Requests for operations to be performed by the members of a group are often referred to as “protocols,” and it is typically through the use of one or more protocols that tasks are cooperatively performed by the members of a group.
Clusters often support changes in group membership through the use of membership change protocols, e.g., if a member job needs to be added to or removed from a group. In some clustered systems, a membership change protocol is implemented as a type of peer protocol, where all members receive a message and each member is required to locally determine how to process the protocol and return an acknowledgment indicating whether the message was successfully processed by that member. Typically, with a peer protocol, members are prohibited from proceeding on with other work until acknowledgments from all members have been received. In other systems, membership change protocols may be handled as master-slave protocols, where one of the members is elected as a leader, and controls the other members so as to ensure proper handling of the protocol.
One particular type of membership change operation that may be implemented in a clustered computer system is a merge, which is required after a group has been partitioned due to a communication loss in the cluster. In particular, a communication loss in a cluster may prevent one or more nodes from communicating with other nodes in the cluster. As such, whenever different member jobs in a group are disposed on different nodes between which communication has been lost, multiple, yet independent instances of the group (referred to as “partitions”) may be formed in the cluster. A merge is therefore used after communication has been reestablished to merge the partitions back together into a single group.
As with communication losses, merges are typically asynchronous with respect to a group—i.e., a merge can occur at any given time. However, even when a group is partitioned due to a communication loss, each partition may still perform useful work. Moreover, a partition typically assumes that, unlike in a node failure instance, any members that have “left” the partition as a result of the partitioning are still active, and are performing useful work. As a consequence, it is necessary whenever a merge occurs to ensure that any ongoing work within a partition is handled in an appropriate manner, and moreover, that ongoing work being performed by multiple partitions is consistent, so that all of the members of the group are “synchronized” with one another upon completion of the merge. Otherwise, conflicts or inconsistencies between different members could occur, resulting in system errors, data corruption, or even system failure.
Given the asynchronous nature of merge operations, conventional clustered computer systems handle such operations immediately upon receipt of a merge request, in an attempt to ensure the merge occurs as quickly as possible to reestablish the original group organization. However, doing so may introduce indeterminate actions, since any ongoing protocols at the time of a merge will be completed after the merge has been processed, and thus after the membership seen by a requesting member has changed.
In addition, conventional clustered computer systems typically utilize master-slave-type protocols to handle merge operations. Master-slave-type protocols, however, are significantly limited in many respects. First, master-slave protocols are susceptible to failure of a leader or master. Second, master-slave protocols often require a centralized data structure to be used in performing a merge, which requires additional communication between nodes, and which can be significantly limited with respect to geographically-dispersed nodes.
Therefore, a significant need exists in the art for an improved manner of handling merge operations to join multiple partitions in a clustered computer system.